"""
二叉树本身是递归结构
思路:
	使用链式存储,一个Node表示一个树的节点
	节点考虑使用两个属性变量分别表示左链接和右链接
"""
from 队列 import *

class Node:
	"""
	二叉树节点,一对二
	"""
	def __init__(self, val, left=None, right=None):
		self.val = val
		self.left = left
		self.right = right


class Bitree:
	"""二叉树遍历类"""
	def __init__(self, root=None):
		self.root = root

	# 先序遍历
	def pre_order(self, node):
		"""先序遍历"""
		if node is None:  # 终止条件 节点
			return
		print(node.val, end='')
		# print(node.left.val)
		self.pre_order(node.left)
		self.pre_order(node.right)

	# 中序遍历
	def in_order(self, node):
		"""中序遍历"""
		if node is None:
			return
		self.in_order(node.left)
		print(node.val, end="")
		self.in_order(node.right)

	# 后序遍历
	def pos_order(self, node):
		"""后序遍历"""
		if node is None:
			return
		self.pos_order(node.left)
		self.pos_order(node.right)
		print(node.val, end="")

	# 层次遍历
	def leve_order(self, node):
		"""
		层次遍历
			:让初始节点先入队,谁出队就遍历谁,并且让他的左右子元素分别入队,直到队列为空
		"""
		sq = SQueue()
		sq.en_queue(node)  # 初始节点
		while not sq.is_empty():
			node = sq.end_queue()
			print(node.val, end='')  # 打印出队元素
			if node.left:
				sq.en_queue(node.left)
			if node.right:
				sq.en_queue(node.right)



if __name__ == '__main__':
	# 根据后续遍历构建二叉树
	b = Node('B')
	f = Node('F')
	g = Node('G')
	d = Node('D', f, g)
	i = Node('I')
	h = Node('H')
	e = Node('E', i, h)
	c = Node('C', d, e)
	a = Node('A', b, c)     # A 树根

	bt = Bitree(a)          # 将a作为遍历的起始位置
	bt.pre_order(bt.root)   # 先序遍历
	print('--------先序遍历----------')
	bt.in_order(bt.root)
	print('--------中序遍历----------')
	bt.pos_order(bt.root)
	print('--------后序遍历----------')
	bt.leve_order(bt.root)
	print('--------层次遍历----------')